/*
 * Created by guoyh on Sun Dec 04 2022 17:35:14
 * leetcode NO. https://leetcode.cn/problems/combination-sum/
 */


#include <iostream>
#include <gtest/gtest.h>
#include<vector>

using namespace std;

void print(vector<int>& path){
    for(int i : path){
        cout<<i<<",";
    }
    cout<<endl;
}

class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<vector<int>> res;
        if(candidates.size() == 0){
            return res;
        }

        vector<int> path;
        backtrack(candidates, res, path, 0, target);

        return res;
    }

    // res: 保存最终结果
    // candidates: 候选数列
    // path：中间结果
    // begin: 搜索起点
    // 搜索目标值
    void backtrack(vector<int>& candidates, vector<vector<int>>& res, vector<int>& path, int begin, int target){
        if(target < 0){
            return;
        }
        if(target == 0){
            res.push_back(path);
            return;
        }

        for(int i = begin; i < candidates.size(); i++){
            target = target - candidates[i];
            path.push_back(candidates[i]);
            print(path);
            cout<<"recursion before: target="<<target<<endl;
            backtrack(candidates, res, path, i, target);

            target = target + candidates[i];
            path.pop_back();
            cout<<"recursion after, backtrack"<<endl;
            print(path);
            cout<<"target="<<target<<endl;
        }

    }
};

TEST(MyTest, AddTest) {
    Solution slu;
    vector<int> candidates = {2,3,6,7};

    vector<vector<int>> res = slu.combinationSum(candidates, 7);

    EXPECT_EQ(res.size(), 2);
}

int main(int argc, char *argv[]) {
    ::testing::InitGoogleTest(&argc, argv);
    return RUN_ALL_TESTS();
}
